Corelab Seminar
2020-2021
Dimitris Achlioptas
Algorithmic Aspects of The Lovász Local Lemma
Abstract.
The Lovász Local Lemma (LLL) is a powerful probabilistic tool for establishing the existence of objects that satisfy certain properties. The breakthrough of Moser and Tardos that made the LLL algorithmic (for which they received the Gödel Prize this year), along with follow-up works revealed that the LLL has intimate connections with a rich class of stochastic local search algorithms. In this talk, I will survey this line of work through the perspective of recent unifying results, and also talk about recent applications to solving constraint satisfaction problems.
Based on joint work with Fotis Iliopoulos and Alistair Sinclair.